#include "algo-busy.h"

#include <QVector>
#include<vector>

#define MAXSIZE 10
#define MAXTIME 999999999

using namespace std;

int n, m;
int min_time = MAXTIME;
int time_table[MAXSIZE][MAXSIZE];
        //bool a[MAXSIZE][MAXSIZE];
        //int b[MAXSIZE];
        //bool c[MAXSIZE];
bool was_job_device[MAXSIZE][MAXSIZE];
int job_device[MAXSIZE];
int cur_time_job[MAXSIZE];
int was_job[MAXSIZE], was_device[MAXSIZE];
vector<int> tmp;
vector<int> tmp2;
int co = 0;

bool can_calculate( void ){
        bool res = true;
        for( int i = 0; i < n; i++ ){
                if( was_job[i] )
                        continue;
                for( int j = 0; j < m; j++ ){
                        if( was_device[j] )
                                continue;
                        res &= was_job_device[i][j];
                }
        }
        return res;
}

bool all_done( void ){
        bool all_d = true;
        for( int i = 0; i < n; i++ )
                for( int j = 0; j < m; j++ )
                        all_d &= was_job_device[i][j];
        return all_d;
}

void solve( int cur_time ){
        if( cur_time > min_time )
                return;

        int _was_job[MAXSIZE], _was_device[MAXSIZE], _cur_time_job[MAXSIZE], _job_device[MAXSIZE];
        for( int i = 0; i < MAXSIZE; i++ ){
                _was_job[i] = was_job[i];
                _was_device[i] = was_device[i];
                _cur_time_job[i] = cur_time_job[i];
                _job_device[i] = job_device[i];
        }

        while( can_calculate() && !all_done() ){
                int m_time = MAXTIME;
                int work;
                for( int i = 0; i < n; i++ )
                        if( (cur_time_job[i] < m_time) && (was_job[i]) ){
                                m_time = cur_time_job[i];
                                //work = i;
                        };
                //was_job[work] = 0;
                //was_device[job_device[work]] = 0;
                cur_time += m_time;
                for( int i = 0; i < n; i++ ){
                        if( was_job[i] )
                                cur_time_job[i] -= m_time;
                        if( !cur_time_job[i] && (was_job[i]) ){
                                was_job[i] = 0;
                                was_device[job_device[i]] = 0;
                        }
                }
        }

        if( all_done() ){
                int max_time = -1;
                for( int i = 0; i < n; i++ )
                        if( cur_time_job[i] > max_time )
                                max_time = cur_time_job[i];
                cur_time += max_time;
                co++;
        }
        if( all_done() && (cur_time < min_time) ){
                min_time = cur_time;
                return;
        }

        for( int i = 0; i < n; i++ ){
                if( was_job[i] )
                                continue;
                for( int j = 0; j < m; j++ ){
                        if( was_device[j] )
                                continue;
                        if( !was_job_device[i][j] ){
                                job_device[i] = j;
                                was_job[i] = 1;
                                was_device[j] = 1;
                                was_job_device[i][j] = 1;
                                cur_time_job[i] = time_table[i][j];
                                if( i == 0 )
                                        tmp.push_back( j );
                                else
                                        tmp2.push_back( j );
                                solve( cur_time );
                                if( i == 0 )
                                        tmp.pop_back( );
                                else
                                        tmp2.pop_back( );
                                job_device[i] = 0;
                                was_job_device[i][j] = 0;
                                was_job[i] = 0;
                                was_device[j] = 0;
                                cur_time_job[i] = 0;
                        }
                }
        }

        for( int i = 0; i < MAXSIZE; i++ ){
                was_job[i] = _was_job[i];
                was_device[i] = _was_device[i];
                cur_time_job[i] = _cur_time_job[i];
                job_device[i] = _job_device[i];
        }
}

int slv( int _n, int _m, QVector<QVector<int> > matrix ){
        //ifstream in;
        //in.open( "input.txt" );

        //in >> n >> m;
        n = _n;
        m = _m;
        for( int i = 0; i < n; i++ )
                for( int j = 0; j < m; j++ )
                        //in >> time_table[i][j];
                        time_table[i][j] = matrix[i][j];

        solve( 0 );

        //ofstream out;
        //out.open( "output.txt" );
        //out << min_time << endl;

        return min_time;

        //cout << min_time << " " << co << endl;
}
